백준 14500 테트로미노

백준 테트로미노는 n * m 배열에 적혀 있는 숫자에 도형을 넣은뒤 도형이 놓여지는 숫자들의 합이 최대로 되게 하는 문제이다. 이 문제는 단순히 도형 하나씩을 넣어보면 되기 때문에 빈틈없이 꽉 채우는 타일링 문제보다 쉬운 것 같다.

먼저 0,0을 기준으로 도형의 상대적인 좌표들로 5개의 도형을 표현 한뒤, rotate, 대칭한 도형들에 대하여 모든 좌표에 대하여 해보는 방법으로 접근했다. 좌표에 대하여 원래 모양의 테트로미노를 넣어보고, 회전한다음에 넣어보고, 대칭한다음 넣어보고 하는 방식으로 최대 값을 찾아가며 모두 해보았다.

좌표에 대하여 2중, 테트로미노 모양에 대하여 1중, 이런식으로 포문을 중첩해서 풀었는데 지금보니까 나도 정말 보기가 힘들다.. 이러한 종류를 짤 때는 for문의 depth가 깊이 들어가지 않도록 작성하도록 해야겠다.

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<functional>
#define INF 999999
using namespace std;

int n, m;



int tetriminoX[5][4] = { { 0,0,0,0 },{ 0,1,1,1 },{ 0,1,1,2 },{ 0,0,0,1 },{ 0,0,1,1 } };
int tetriminoY[5][4] = { { 0,1,2,3 },{ 0,0,1,2 },{ 0,0,1,1 },{ 0,1,2,1 },{ 0,1,0,1 } };
int map[500][500];

void rotate(int& x, int& y)
{
	int temp = x;
	x = y;
	y = -temp;
}

void xSymet(int& y)
{
	y = -y;
}

int isOk(int s, int e, int x[4], int y[4])
{
	for (int i = 0; i < 4; i++)
	{
		if (0 <= s + x[i] && s + x[i] < n && 0 <= e + y[i] && e + y[i] < m)
		{
		}
		else
			return false;
	}

	return true;
}

int main()
{
	//freopen("input.txt", "r", stdin);

	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			scanf("%d", &map[i][j]);
	}

	int max = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			for (int k = 0; k < 5; k++) // 테트로미노 모양
			{
				for (int c = 0; c < 2; c++)
				{
					for (int l = 0; l < 4; l++) // 회전
					{

						if (isOk(i, j, tetriminoX[k], tetriminoY[k]))
						{
							int sum = 0;
							for (int o = 0; o < 4; o++)
							{
								sum += map[i + tetriminoX[k][o]][j + tetriminoY[k][o]];

							}
							if (max < sum)
								max = sum;
						}
						for (int z = 0; z < 4; z++)
							rotate(tetriminoX[k][z], tetriminoY[k][z]);
					}

					for (int i = 0; i < 5; i++)
					{
						for (int j = 0; j < 4; j++)
							xSymet(tetriminoY[i][j]);
					}

				}
			}
		}
	}



	printf("%d\n", max);
}